class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class RotateList {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || k == 0) return head;

        // 计算链表的长度
        ListNode current = head;
        int length = 1;
        while (current.next != null) {
            current = current.next;
            length += 1;
        }

        // 形成环
        current.next = head;

        // 找到新的头和尾的位置
        k = k % length;
        int stepsToNewHead = length - k;
        ListNode newTail = current;
        while (stepsToNewHead-- > 0) {
            newTail = newTail.next;
        }
        ListNode newHead = newTail.next;

        // 断开环
        newTail.next = null;

        return newHead;
    }

    public static void main(String[] args) {
        RotateList rl = new RotateList();

        // 创建一个链表 1->2->3->4->5
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);

        // 旋转链表 k=2
        ListNode result = rl.rotateRight(head, 2);

        // 输出旋转后的链表
        while (result != null) {
            System.out.print(result.val + " ");
            result = result.next;
        }
    }
}
